class Solution {
public:
    int INF=0x3f3f3f3f;
    int minDistance(vector<int>& houses, int k) {
        int n = houses.size();
        vector<int> dp(n+1, INF);
        sort(houses.begin(), houses.end());
        vector<int> sum(1);
        for(int i:houses)
            sum.push_back(sum.back()+1);

        auto cost = [&](int i,int j) {
            int mi = (i+j) / 2;
            return houses[mi - 1] * (mi*2-i-j+1) + sum[i -1] + sum[j] - sum[mi] * 2;
        };

        dp[0] = 0;
        for(int i = 1; i <= k; i ++)
            for(int j = n; j >= 1; j--)
                for(int l = 0; l < j; l++) 
                    dp[j] = min(dp[j], dp[l] + cost(l+1,j));
        return dp[n];
    }
};